/**
 * Projeto final de Programacao Concorrente.
 * Prof. Dr. Julio Estrella
 * 
 * Geracao aleatoria de palavras.
 * 
 * Grupo 07 - Turma B
 * Fabio de Albuquerque Dela Antonio 6792558
 * Leonardo Henrique Omoto 6793160
 * Pedro Paulo Canto Martucci 6793100
 * 
 * main.cu
 */

#include "header.h"
#include "hashMap.h"
#include "tempo.h"

/* Vetor global de divisoes do espaco aleatorio
 * (utilizado para que palavras aleatorias de
 * tamanhos diferentes tenham a mesma chance de
 * serem sorteadas) 
 */
unsigned long division[MAX_LENGHT_WORD];

/* Prototipos das funcoes */
void preProcess();
int getSize();    

/* Funcoes na GPU */
#ifndef SEQUENCIAL

#include <curand.h>
#include <curand_kernel.h>

/**
 * Inicializa numeros aleatorios
 */
__global__ void setupRand(curandState *state, int seed)
{
    int id = threadIdx.x + blockIdx.x * blockDim.x;
    curand_init(seed, id, 0, &state[id]);
}

/**
 * Gera numero aleatorio
 */
__device__ unsigned long getRand(curandState *state) {
    int id = threadIdx.x;
    curandState localState = state[id];
    unsigned long randNumber = curand(&localState);
    state[id] = localState;
    return randNumber;
}

/**
 * Obtem numero randomico para tamanho de palavra (GPU)
 */
__device__ int getSizeGPU(unsigned long * divisionGPU, curandState * state) 
{
    unsigned long size = getRand(state);
    int i;

    /* Compara o valor aleatorio com as divisoes (do pre-processamento) 
     * e atribui valor de tamanho da palavra com base no numero da 
     * divisao onde o numero aleatorio se encaixa.
     */
    for(i = 0; i < MAX_LENGHT_WORD; i++)
        if(size < divisionGPU[i])
            return (i + 1);

    return 0;
}


/**
 * Compara duas strings e retorna verdadeiro caso sejam iguais
 */
__device__ int strCompare(const char *s1, const char *s2)
{
    while (*s1==*s2)
    {
        if(*s1=='\0')
            return 0;
        s1++;
        s2++;
    }

    return (*s1-*s2);
}

/**
 * Realiza a busca binaria na estrutura de palavras e retorna o seu indice
 */
__device__ int binarySearch(regWord *rw, char * word ,int size )
{
    int imin = 0;
    int imax = size;
    int imid, result;

    /* Continua a busca enquanto o intervalo [imin, imax] nao estiver vazio */
    while (imax >= imin)
    {
        imid = (imin + imax) / 2;
 
        result = strCompare(rw[imid].word, word);   

        if(result <  0)
            imin = imid + 1;
        else if (result >  0)
            imax = imid - 1;
        else
            return imid;
    }
    
    return -1;
}

/**
 * Sorteia palavras na GPU
 */
__global__ void gpuProcess(curandState * state, regWord * rw, unsigned long * divisionGPU, int * found, int size) 
{

    int wordSize = getSizeGPU(divisionGPU, state);
    char word[MAX_LENGHT_WORD+1];
    int i, index, result = 0;
    
    for(i = 0; i < wordSize; ++i)
        word[i] = (char)((getRand(state) % 26) + 'a');       
    
    word[i] = '\0';
    
    index = binarySearch(rw, word, size);    
    
    if(index != -1) {
        result = atomicCAS(&(rw[index].state), NOT_FOUND, FOUND);
        
        if(result == NOT_FOUND)
            atomicInc((unsigned int *)found, size + 1);
    }

}

#endif

/**
 * Funcao principal do programa
 */
int main(int argc, const char *argv[]) {

    Tempo total;

#ifdef SEQUENCIAL
    if(argc != 2) {
        cerr << "Uso: " << argv[0] << " <arquivo de palavras>\n";
        return 1;
    }

#else
    if(argc != 4) {
            cerr << "Uso: " << argv[0] << " <arquivo de palavras> <numero de blocos> <numero de threads>\n";
            return 1;
        }

#endif
    /* Vetor de porcentagens. */
    int percents[10];

    /* Numero de palavras encontradas */
    int found = 0;
    
    int i = 0, j = 0;

    /* Faz pre-processamento para que palavras de tamanhos
     * diferentes tenham a mesma chance de serem sorteadas.
     * (gera vetor de divisoes) 
     */    
    preProcess();

    /* Carrega palavras do arquivo na base de dados (hashMap) */
    hashMap h(argv[1]);

    cout << "Total de palavras distintas carregadas: " << h.getWords() << "\n";

    /* Preenche vetor de porcentagens */
    for( i = 0; i < 9; i++ )
        percents[i] = (h.getWords()/10)*(i + 1); 
    percents[9] = h.getWords();

#ifdef SEQUENCIAL
    /* Inicio contagem de tempo */
    Tempo t;

    /* Processamento sequencial */
    srand(time(NULL));

    /* Enquanto existirem palavras na base de dados (ainda nao encontradas) */
    while(!h.done()) {

        char character;
        int wordSize = getSize();
        string word;

        /* Gera palavra randomicamente */
        for(i = 0; i < wordSize; i++) {
            character = (char)((rand() % 26) + 'a');
            word.push_back(character);
        }

        /* Verifica se palavra randomica esta na base de dados */
        found = h.check(word);

        if(found >= percents[j])
        {
            cout << (j + 1)*10 << "% " << "Palavras: " << found << " Tempo: " << t.getMiliseconds() << " ms" << "\n";
            j++;
        }
        
        /* Apaga palavra */
        word.erase();
    }

#else
    /* Processamento na placa de video */
    regWord * rw;

    int N_BLOCOS = atoi(argv[2]);
    int N_THREADS = atoi(argv[3]);
    
    /* Aloca vetor de palavras */
    if((rw = (regWord *)malloc(h.getWords()*sizeof(regWord))) == NULL) {
        cerr << "Impossivel alocar vetor local de palavras.\n";
        return 1;
    }

    /* Copia a estrura hashMap para a estrutura utilizada na placa */
    i = 0;
    
    for(map<string,int>::iterator it = h.getBegin(); it != h.getEnd(); it++)
    {
        strcpy(rw[i].word, h.getWord(it).c_str());
        rw[i].state = NOT_FOUND;
        i++;
    }

    /* Ponteiro logico dos dados na memoria da GPU */
    regWord * rw_gpu;
    int * foundWords;
    unsigned long * divisionGPU;

    /* Estado para numeros aleatorios (CUDA) */
    curandState * devState;

    /* Alocando na memoria da GPU */
    if( cudaMalloc(&rw_gpu, h.getWords()*sizeof(regWord)) != cudaSuccess )
    {
        cerr << "Impossivel alocar vetor de palavras na memoria da GPU.\n";
        return 1;
    }

    if( cudaMalloc(&foundWords, sizeof(int)) != cudaSuccess )
    {
        cerr << "Impossivel alocar contador de palavras na memoria da GPU.\n";
        return 1;
    }

    if( cudaMalloc(&divisionGPU, MAX_LENGHT_WORD*sizeof(unsigned long)) != cudaSuccess )
    {
        cerr << "Impossivel alocar vetor de divisoes na memoria da GPU.\n";
        return 1;
    }

    if( cudaMalloc(&devState, N_BLOCOS*sizeof(curandState)) != cudaSuccess )
    {
        cerr << "Impossivel alocar estados para numeros aleatorios.\n";
        return 1;
    }

    /* Copiando para a memoria da GPU */
    if( cudaMemcpy(rw_gpu, rw, h.getWords()*sizeof(regWord), cudaMemcpyHostToDevice) != cudaSuccess )
    {
        cerr << "Impossivel copiar vetor de palavras para memoria da GPU.\n";
        return 1;
    }

    if( cudaMemcpy(foundWords, &found, sizeof(int), cudaMemcpyHostToDevice) != cudaSuccess )
    {
        cerr << "Impossivel copiar contador de palavras para memoria da GPU.\n";
        return 1;
    }

    if( cudaMemcpy(divisionGPU, division, MAX_LENGHT_WORD*sizeof(unsigned long), cudaMemcpyHostToDevice) != cudaSuccess )
    {
        cerr << "Impossivel copiar vetor de divisoes para memoria da GPU.\n";
        return 1;
    }

    /* Inicio da contagem do tempo. */
    Tempo t;
    
    /* Inicializa numeros randomicos */
    setupRand<<<N_BLOCOS, N_THREADS>>>(devState, time(NULL));

    i = 0; j= 0; found = 0;

    /* Loop de Execucao*/
    while(found < h.getWords())
    {
        gpuProcess<<<N_BLOCOS, N_THREADS>>>(devState, rw_gpu, divisionGPU, foundWords, h.getWords());
        
        if( i > 5 )
        {
            if( cudaMemcpy(&found, foundWords, sizeof(int), cudaMemcpyDeviceToHost) != cudaSuccess )
            {
                cerr << "Impossivel copiar o contador de palavras encontradas para a CPU.\n";
                return 1;
            }
            
            if(found >= percents[j])
            {
                cout << (j + 1)*10 << "% " << "Palavras: " << found << " Tempo: " << t.getMiliseconds() << " ms" << "\n";
                j++;
            }
            i = 0;
        }
        i++;
        
    }

    /* Desalocacao de memoria da GPU e da CPU */
    cudaFree(rw_gpu);
    cudaFree(foundWords);
    cudaFree(divisionGPU);
    free(rw);
    
#endif

    cout << "tempo total: " << total.getMiliseconds() << " ms" << "\n";

    return 0;
}

/**
 * Faz pre-processamento para que palavras de tamanho distintos
 * tenham a mesma chance de serem sorteadas.
 */
void preProcess() {

    float sum = 0;
    float div[MAX_LENGHT_WORD];

    for(int i = 0; i < MAX_LENGHT_WORD; i++) {
        div[i] = pow(26,(i+1));
        sum += div[i];
    }

    
    for(int i = 0; i < MAX_LENGHT_WORD; i++) {
        div[i] /= sum;
        if(i > 0)
            div[i] += div[i-1];
    }

    for(int i = 0; i < MAX_LENGHT_WORD; i++) {
#ifdef SEQUENCIAL
        division[i] = roundf(div[i]*RAND_MAX);
#else
        division[i] = roundf(div[i]*RAND_MAX_CUDA);
#endif
    }

    

}

/**
 * Funcao para se obter um tamanho de palavra.
 * Este tamanho devera ser utilizado como o tamanho da
 * palavra aleatoria gerada.
 */
int getSize() {
    int size = rand();

    /* Compara o valor aleatorio com as divisoes (do pre-processamento) 
     * e atribui valor de tamanho da palavra com base no numero da 
     * divisao onde o numero aleatorio se encaixa.
     */
    for(int i = 0; i < MAX_LENGHT_WORD; i++)
        if(size < division[i])
            return (i + 1);

    return 0;
}

